package org.algorithm.二师兄.链表;

import org.algorithm.common.ListNode;

/**
 *  区间反转
 */
public class 反转链表2 {

    public static void main(String[] args) {

        ListNode node = ListNode.build(1,2,5,4,3,6);
        ListNode.print(node);
        System.out.println();

        node = reverseListNode(node, 2, 5);
        ListNode.print(node);
    }

    private static ListNode reverseListNode(ListNode node, int m, int n) {
        if (node == null || node.next == null) return node;
        if (m >= n) return node;

        ListNode dummy = new ListNode(-1);
        dummy.next = node;
        // 找到m的位置
        ListNode head = dummy;
        ListNode prev = dummy.next;
        for (int i = 0; i < m - 1; i++) {
            head = head.next; prev = prev.next;
        }

        // 从 n -> m 之间转换
        for (int i = 0; i < n - m; i++) {
            ListNode temp = prev.next;
            prev.next = prev.next.next;
            temp.next = head.next;
            head.next = temp;
        }
        return dummy.next;
    }
}
